# 给定一个只包括 '('，')'，'{'，'}'，'['，']'的字符串 s ，判断字符串是否有效。
# 有效字符串需满足：
# 左括号必须用相同类型的右括号闭合。
# 左括号必须以正确的顺序闭合。
# 每个右括号都有一个对应的相同类型的左括号。


class Solution(object):
    def isValid(self, s):
        """
        :type s: str
        :rtype: bool
        """
        dic = {
            ")": "(",
            "}": "{",
            "]": "["
        }
        stack = []
        for i in range(len(s)):
            if s[i] == "(" or s[i] == "{" or s[i] == "[":
                stack.append(s[i])
            else:
                if not stack:
                    return False
                if stack.pop() != dic[s[i]]:
                    return False
        if not stack:
            return True
        else:
            return False


if __name__ == '__main__':
    s = ")"
    solution = Solution()
    res = solution.isValid(s)
    print(res)